package com.gwcloud.leetcode.tags.array;

import com.gwcloud.leetcode.common.CommonUtils;

/** 
* @ClassName   : Leetcode1010 
* @author      : ganwei 
* @date        : 2020年4月29日 
* @Description : Leetcode 1010 总持续时间可被 60 整除的歌曲 
*/
public class Leetcode1010 {

	/**
	 * 解题思路1-暴力解法 O(NLog(N))
	 * 优点：简单
	 * 缺点：不满足leetcode时间要求
	 * 
	 */
    public static int numPairsDivisibleBy60(int[] time) {
    	int count = 0;
    	for(int i = 1; i < time.length; i++) {
    		for(int j = 0; j < i; j++ ) {
    			if((time[i]+time[j]) % 60 == 0) {
    				count++;
    			}
    		}
    	}
    	
    	return count;
    }
    
    /**
     * 解题思路2-牛的一批 O(N)
     * 优点：计算复杂度优化到极致
     * 缺点：无
     * 思路：    
     * 1.整数对60取模，可能有60种余数。故初始化一个长度为60的数组，统计各余数出现的次数。
     * 2.遍历time数组，每个值对60取模，并统计每个余数值（0-59）出现的个数。因为余数部分需要找到合适的cp组合起来能被60整除。
     * 3.余数为0的情况，只能同余数为0的情况组合（如60s、120s等等）。0的情况出现k次，则只能在k中任选两次进行两两组合。
     * 4.本题解单独写了个求组合数的方法，也可以用k * (k - 1) / 2表示。余数为30的情况同上。
     * 5.其余1与59组合，2与58组合，故使用双指针分别从1和59两头向中间遍历。1的情况出现m次，59的情况出现n次，则总共有m*n种组合。
     */

    
    public static int numPairsDivisibleBy60_1(int[] time) {
    	int count = 0;
    	int[] newtime = new int[60];
    	for(int t : time) {
    		newtime[t % 60] += 1;
    	}
    	count += CommonUtils.combination(newtime[0], 2);
    	count += CommonUtils.combination(newtime[30], 2);
    	
    	int i = 1, j = 59;
    	while(i<j) {
    		count += newtime[i++] * newtime[j--];
    	}
    	
    	return count;
    }
    
    
	public static void main(String args[]) {
		int[] time = {30,20,150,100,40};
		System.out.println(numPairsDivisibleBy60_1(time));
	}
}
